public class LeetCode_Question_1163 {

    // 1163. 按字典序排在最后的子串
    // 困难

    /*
给你一个字符串 s，找出它的所有子串并按字典序排列，返回排在最后的那个子串。

示例 1：

输入："abab"
输出："bab"
解释：我们可以找出 7 个子串 ["a", "ab", "aba", "abab", "b", "ba", "bab"]。按字典序排在最后的子串是 "bab"。
示例 2：

输入："leetcode"
输出："tcode"
 

提示：

1 <= s.length <= 4 * 10^5
s 仅含有小写英文字符。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/last-substring-in-lexicographical-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
    * */

    public static void main(String[] args) {
        System.out.println(new Solution2().lastSubstring("abab"));
    }

}

/**
 * 1.找出它的所有子串
 * 2.按字典序排列
 */
class MySolution{

}

class Solution1 {
    public String lastSubstring(String s) {

        char[] str = s.toCharArray();
        int index = str.length-1;
        int max = 0;

        for(int i=str.length-1;i>=0;i--){
            if(str[i]-'a'>max){
                index = i;
                max = str[i]-'a';
            }else if(str[i]-'a'==max){
                if(i-1>=0&&str[i]==str[i-1]) continue;//非常关键！！！
                int temp = index;
                index = i;
                max = str[i]-'a';
                for(int j=i,k=temp;j<str.length&&k<str.length;j++,k++){
                    if(str[k]-'a'==str[j]-'a') continue;
                    if(str[k]-'a'>str[j]-'a'){
                        index = temp;
                        max = str[index]-'a';
                        break;
                    }else if(str[k]-'a'<str[j]-'a'){
                        break;
                    }
                }
            }
        }

        return s.substring(index);
    }
}

class Solution2{
    public String lastSubstring(String s) {
        if (s == null || s.length() == 0) {
            return "";
        }
        int maxPrefix = s.charAt(0);
        int maxPrefixIndex = 0;

        int maxSearch = 0;

        int cmpIndex = -1;

        int cur = 1;

        while(cur < s.length()) {
            int curChar = s.charAt(cur);
            if (curChar > maxPrefix) {
                maxPrefix = curChar;
                maxPrefixIndex = cur;
                maxSearch = maxPrefixIndex;
                cmpIndex = -1;
            } else if (cmpIndex > 0) {
                int prefixCmpChar = s.charAt(++maxSearch);
                if (curChar < prefixCmpChar) {
                    maxSearch = maxPrefixIndex;
                    cmpIndex = -1;
                } else if (curChar > prefixCmpChar) {
                    maxPrefixIndex = cmpIndex;
                    maxSearch = maxPrefixIndex;

                    cmpIndex = -1;
                } else if (curChar == maxPrefix && s.charAt(maxSearch - 1) != maxPrefix){
                    maxSearch = maxPrefixIndex;
                    cmpIndex = cur;
                }
            } else if(curChar == maxPrefix) {
                cmpIndex = cur;
            }
            cur++;
        }
        return s.substring(maxPrefixIndex);
    }

}